import java.util.ArrayList;
import java.util.List;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-12-21
 * Time: 0:04
 */
class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    public static ListNode ReverseList(ListNode head) {
        //方法一：三指针法
        /*
        if(head==null || head.next==null){
            return head;
        }
        ListNode left=head;
        ListNode mid=left.next;
        ListNode right = mid.next;
        while(right!=null){
            //翻转
            mid.next=left;
            left=mid;
            mid=right;
            right=right.next;
        }
        //进行翻转之后，由于我们是翻转，再后移，然后再判断，所以在后移过程中，right可能出现null,所以就进不去循环，完成不了最后一次翻转
        //要另外判断
        //先翻转
        mid.next=left;
        //因为left最初在head,然后一直在往后走，但是原来的head没动，所以要原来的头节点变成尾结点，置为空
        head.next=null;
        //指向mid
        head=mid;
        return head;*/

        //头插法，相当给一个新的链表的头节点，然后拿着原链表的每一个节点插在新的链表节点的前面
        if(head==null || head.next==null){
            return head;
        }
        //定义新链表的头结点
        ListNode newHead=null;
        //遍历老的链表，让头结点一直往后走
        while(head!=null){
            //p节点用于连接新的链表节点
            ListNode p=head;
            //头结点往后走
            head = head.next;

            //头插法插入新的链表
            p.next=newHead;
            newHead=p;
        }
        //遍历到了旧链表的结尾，说明翻转完成，返回新的头结点
        return  newHead;
    }

}
